#include <iostream>
#include <random>

using namespace std;
//好习惯

//额 本来应该用template来写一个更有健壮性的排序，但是我补天快来不及了，就算了
//好吧 还是写一下

//这是一个简单排序，我最终用了冒泡

template<typename Comparable>
void simpleSort(vector<Comparable> & a)
{
  for(int i = 0;i < a.size();++i)
    {
      int index = 1;
      for(int j=i+1;j <a.size();++j)
	{
	  if(a[i] < a[j])
	    {
	      index = j;
	    }
	}

      Comparable tmp = move(a[index]);
      a[index] = move(a[i]);
      a[i] = move(tmp);
    }
}
//没搞错的话move是这么用的 然后已经using namespace了 就不需要 std：：move了似乎?

//下面是两个策略的QS

template< typename Comparable>
//没找到代码，抄书好累
void quicksort_mid(vector <Comparable> & a,int l,int r)
{
  if(left + 10 <= right)
    {
      const Comparable & pivot = median3(a,left,right);
      int i = left,j = right - 1;
      for(;;)
	{
	  while(a[++i] < pivot){}
	  while(pivot < a[--j]){}
	  if(i<j)
	    swap(a[i],a[j]);
	  else
	    break;
	}
      
      swap(a[i],a[right - 1]);
      quicksort_mid(a,left,i-1);
      quicksort_m(a,i+1,right);
    }
  else
    simpleSort(a);
}

template <typename Comparable>
const Comparable & median3(vector<Comparable> & a,int left,int right)
{
  int center = (left+right)/3;
  if(a[center]<a[left])
    swap(a[center],a[left]);
  if(a[right] < a[left])
    swap(a[right],a[left]);
  if(a[right] < a[center])
    swap(a[right],a[center]);
  swap(a[center],a[right - 1]);
  return a[right - 1];
}

//取中的写过了 然后写一个随机的版本

template<typename Comparable>

const Comparable & random(vector<Comparable> & a)
{
  int ran = rand() % a.size();
  //没记错可以这样，随机产生，不过不能指定范围的randu用起来真不方便（或许？）
  return a[ran];
}

template<typename Comparable>
void quicksort_ran(vector<Comparable> & a,int left,int right)
{
  if(left + 10 <= right)
    {
      const Comparable & pivot = random(a);
      int i = left,j = right - 1;
      for(;;)
        {
          while(a[++i] < pivot){}
          while(pivot < a[--j]){}
          if(i<j)
            swap(a[i],a[j]);
          else
            break;
        }

      swap(a[i],a[right - 1]);
      quicksort_mid(a,left,i-1);
      quicksort_m(a,i+1,right);
    }
  else
    simpleSort(a);

}
//可以复制 好爽
//下面是为了主程序舒服，再套一层

template <typename Comparable>
void quicksort_r(vector<Comparable> & a)
{
  quicksort_ran(a,0,a.size()-1);
}
//为什么呢，因为写完了才想起来可以把left和right初始化，但是不想对已经写好的东西乱动了
template <typename Comparable>

void quicksort_m(vector<Comparable> & a)
{
  quicksort_mid(a,0,a.size() - 1);
}


